"""
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
"""
path = []
used = []
depth = 0
res = []
# 深度优先搜索
def dfs(nums, depth, path, used, res):
    # 已经到了叶子节点
    if(depth == len(nums)):
        res.append(path.copy())
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        # 还没被选过
        path.append(nums[i])
        used[i] = True
        dfs(nums, depth + 1, path, used, res)
        # 回溯
        path.pop()
        used[i] = False
class Solution:
    def permute(self, nums):
        for _ in range(len(nums)):
            used.append(False)
        if len(nums) == 0:
            return res
        dfs(nums, depth, path, used, res)
        return res

# print(Solution.permute(self=None, nums = [1,2,3]))